package leetCode.solution;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x
 * 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * 
 * @author jerry
 * @ClassName: Solution236
 * @Description:
 * @date 2022年11月11日 下午3:44:57
 */
public class Solution236 {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		return process(root, p, q).r;
	}

	// 暴力递归
	private Info process(TreeNode cur, TreeNode p, TreeNode q) {
		if (cur == null)
			return new Info(false, null);

		Info leftInfo = process(cur.left, p, q);
		if (leftInfo.r != null)
			return leftInfo;
		Info rightInfo = process(cur.right, p, q);
		if (rightInfo.r != null)
			return rightInfo;

		// 3 containsWithTwoBranch
		if (leftInfo.containsOne == true && rightInfo.containsOne == true
				|| ((leftInfo.containsOne == true || rightInfo.containsOne == true) && (cur == p || cur == q))) {
			return new Info(true, cur);
		}
		// 2 contains one
		if (leftInfo.containsOne == true || rightInfo.containsOne == true || cur == p || cur == q) {
			return new Info(true, null);
		}
		return new Info(false, null);

	}

	private class Info {
		boolean containsOne;
		TreeNode r;

		public Info(boolean containsOne, TreeNode r) {
			super();
			this.containsOne = containsOne;
			this.r = r;
		}
	}
	
	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}